#include<vector>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
private:

    ListNode* mergeSort(ListNode* head) {
        if (head == NULL||head->next==NULL) return head;
        ListNode node(-1);
        node.next = head;
        ListNode* first=&node, *second=&node;
        while (second != NULL&&second->next!=NULL) {
            first = first->next;
            second = second->next;
            if (second != NULL)
                second = second->next;
        }
        second = first->next;
        first->next = NULL;
        first=mergeSort(head);
        second=mergeSort(second);
        ListNode* res = &node;
        while (first != NULL && second != NULL) {
            if (first->val <= second->val) {
                res->next = first;
                first = first->next;
            }
            else {
                res->next = second;
                second = second->next;
            }
            res = res->next;
        }
        if (first != NULL) 
            res->next = first;
        else
            res->next = second;
        return node.next;
    }

public:
    ListNode* sortList(ListNode* head) {
        return mergeSort(head);
    }
};